/**
 * 221. 最大正方形
 * https://leetcode-cn.com/problems/maximal-square/
 */

/**
 * @param {string[][]} matrix
 * @return {number}
 */
function maximalSquare(matrix) {
  const { length: m } = matrix;
  const { length: n } = matrix[0];
  const dp = new Array(m);
  for (let i = 0; i < m; i += 1) {
    dp[i] = new Array(n).fill(0);
  }
  let max = 0;
  for (let i = 0; i < m; i += 1) {
    if (matrix[i][0] === '1') {
      dp[i][0] = 1;
      max = 1;
    }
  }
  for (let j = 1; j < n; j += 1) {
    if (matrix[0][j] === '1') {
      dp[0][j] = 1;
      max = 1;
    }
  }
  for (let i = 1; i < m; i += 1) {
    for (let j = 1; j < n; j += 1) {
      if (matrix[i][j] === '1') {
        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
        max = Math.max(max, dp[i][j]);
      }
    }
  }
  return max * max;
}

console.log(maximalSquare([
  ['1', '0', '1', '0', '0'],
  ['1', '0', '1', '1', '1'],
  ['1', '1', '1', '1', '1'],
  ['1', '0', '0', '1', '0'],
]) === 4);
console.log(maximalSquare([['0', '1'], ['1', '0']]) === 1);
console.log(maximalSquare([['0']]) === 0);
